package com.mlh.dp.old;
/*
题目：给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

举例：输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
        输出：11
        解释：如下面简图所示：
        2
       3 4
      6 5 7
     4 1 8 3
 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
*/

import java.util.Iterator;
import java.util.List;

public class TriangleMinimumPathSum {
    //暴力递归
    //当前位置的最小路径和
    public static int method1(List<List<Integer>> triangle,int row,int col){
        if(row>=triangle.size()-1){
            return triangle.get(triangle.size()-1).get(col);
        }
        return Math.min(method1(triangle,row+1,col),method1(triangle,row+1,col+1))+triangle.get(row).get(col);

    }

    //记忆搜索
    public static int method2(List<List<Integer>> triangle,int row,int col,int[][]res){
        if(res[row][col]!= Integer.MAX_VALUE){
            return res[row][col];
        }
        if(row>=triangle.size()-1){
            res[row][col]=triangle.get(triangle.size()-1).get(col);
            return res[row][col];
        }
        res[row][col]=Math.min(method2(triangle,row+1,col,res),method2(triangle,row+1,col+1,res))+triangle.get(row).get(col);
        return res[row][col];

    }
    //这边发现了一个记忆搜索到严格表依赖转换的一个问题
    //记忆搜索有可能会试探到 被赋值和未被赋值的地方  因此我们需要初始化某些数值来区分这两种情况
    //而严格表依赖不会去试探到某被赋值的地方或者不合法的地方 因此并不需要进行初始化操作

    //严格表依赖
    public static int method2(List<List<Integer>> triangle){
        int[][]res=new int[triangle.size()][triangle.size()];
        for(int i=triangle.size()-1;i>=0;i--){
            for(int j=0;j<=i;j++){
               if(i==triangle.size()-1){
                   res[i][j]=triangle.get(i).get(j);
               }else{
                   res[i][j]=Math.min(res[i+1][j],res[i+1][j+1])+triangle.get(i).get(j);
               }
            }
        }
        return res[0][0];
    }

}
